package com.example.lettcode._202412._20241219;

/*
680. 验证回文串 II
给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：
输入：s = "aba"
输出：true

示例 2：
输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。

示例 3：
输入：s = "abc"
输出：false

提示：
1 <= s.length <= 105
s 由小写英文字母组成
 */
public class _680_yan_zheng_hui_wen_chuan_2 {

    public static void main(String[] args) {
        String s = "abca";
        System.out.println(validPalindrome2(s));
    }

    public static boolean validPalindrome(String s) {
        int[] ints = new int[26];
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            ints[aChar - 'a']++;
        }

        int ret = 0;
        for (int anInt : ints) {
            if (anInt % 2 != 0) {
                ret++;
                if (ret > 2) {
                    return false;
                }
            }
        }
        return true;
    }

    public static boolean validPalindrome2(String s) {
        int left = 0, right = s.length()-1;
        char[] chars = s.toCharArray();
        while (left < right) {
            if (chars[left] == chars[right]) {
                left++;
                right--;
            } else {
                return deleteChar(chars, left+1, right) || deleteChar(chars, left, right-1);
            }
        }
        return true;
    }

    private static boolean deleteChar(char[] chars, int left, int right) {
        while (left < right) {
            if (chars[left] == chars[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}
